home *** CD-ROM | disk | FTP | other *** search
/ Disc to the Future 2 / Disc to the Future Part II Programmer's Reference (Wayzata Technology)(6013)(1992).bin / MAC / THINKC / 4_0 / GAWK-2 / ARRAY.C < prev    next >
Text File  |  1992-07-19  |  6KB  |  270 lines
  1. /*
  2.  * array.c - routines for associative arrays.
  3.  */
  4.  
  5. /* 
  6.  * Copyright (C) 1986, 1988, 1989 the Free Software Foundation, Inc.
  7.  * 
  8.  * This file is part of GAWK, the GNU implementation of the
  9.  * AWK Progamming Language.
  10.  * 
  11.  * GAWK is free software; you can redistribute it and/or modify
  12.  * it under the terms of the GNU General Public License as published by
  13.  * the Free Software Foundation; either version 1, or (at your option)
  14.  * any later version.
  15.  * 
  16.  * GAWK is distributed in the hope that it will be useful,
  17.  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  18.  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  19.  * GNU General Public License for more details.
  20.  * 
  21.  * You should have received a copy of the GNU General Public License
  22.  * along with GAWK; see the file COPYING.  If not, write to
  23.  * the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.
  24.  */
  25.  
  26. #include "awk.h"
  27.  
  28. #ifdef DONTDEF
  29. Int primes[] = {31, 61, 127, 257, 509, 1021, 2053, 4099, 8191, 16381};
  30. #endif
  31.  
  32. #define ASSOC_HASHSIZE 127
  33. #define STIR_BITS(n) ((n) << 5 | (((n) >> 27) & 0x1f))
  34. #define HASHSTEP(old, c) ((old << 1) + c)
  35. #ifndef THINK_C
  36. #define MAKE_POS(v) (v & ~0x80000000)    /* make number positive */
  37. #else
  38. #define MAKE_POS(v) (v & ~0x8000) /* make 16 bit int positive */
  39. #endif
  40.  
  41. NODE *
  42. concat_exp(tree)
  43. NODE *tree;
  44. {
  45.     NODE *r;
  46.     char *str;
  47.     char *s;
  48.     unsigned len;
  49.     int offset;
  50.     int subseplen;
  51.     char *subsep;
  52.  
  53.     if (tree->type != Node_expression_list)
  54.         return force_string(tree_eval(tree));
  55.     r = force_string(tree_eval(tree->lnode));
  56.     if (tree->rnode == NULL)
  57.         return r;
  58.     subseplen = SUBSEP_node->lnode->stlen;
  59.     subsep = SUBSEP_node->lnode->stptr;
  60.     len = r->stlen + subseplen + 1;
  61.     emalloc(str, char *, len, "concat_exp");
  62.     memcpy(str, r->stptr, r->stlen+1);
  63.     s = str + r->stlen;
  64.     free_temp(r);
  65.     tree = tree->rnode;
  66.     while (tree) {
  67.         if (subseplen == 1)
  68.             *s++ = *subsep;
  69.         else {
  70.             memcpy(s, subsep, subseplen+1);
  71.             s += subseplen;
  72.         }
  73.         r = force_string(tree_eval(tree->lnode));
  74.         len += r->stlen + subseplen;
  75.         offset = s - str;
  76.         erealloc(str, char *, len, "concat_exp");
  77.         s = str + offset;
  78.         memcpy(s, r->stptr, r->stlen+1);
  79.         s += r->stlen;
  80.         free_temp(r);
  81.         tree = tree->rnode;
  82.     }
  83.     r = tmp_string(str, s - str);
  84.     free(str);
  85.     return r;
  86. }
  87.  
  88. /* Flush all the values in symbol[] before doing a split() */
  89. void
  90. assoc_clear(symbol)
  91. NODE *symbol;
  92. {
  93.     int i;
  94.     NODE *bucket, *next;
  95.  
  96.     if (symbol->var_array == 0)
  97.         return;
  98.     for (i = 0; i < ASSOC_HASHSIZE; i++) {
  99.         for (bucket = symbol->var_array[i]; bucket; bucket = next) {
  100.             next = bucket->ahnext;
  101.             deref = bucket->ahname;
  102.             do_deref();
  103.             deref = bucket->ahvalue;
  104.             do_deref();
  105.             freenode(bucket);
  106.         }
  107.         symbol->var_array[i] = 0;
  108.     }
  109. }
  110.  
  111. /*
  112.  * calculate the hash function of the string subs, also returning in *typtr
  113.  * the type (string or number) 
  114.  */
  115. static int
  116. hash_calc(subs)
  117. NODE *subs;
  118. {
  119.     register int hash1 = 0, i;
  120.  
  121.     subs = force_string(subs);
  122.     for (i = 0; i < subs->stlen; i++)
  123.         hash1 = HASHSTEP(hash1, subs->stptr[i]);
  124.  
  125.     hash1 = MAKE_POS(STIR_BITS((int) hash1)) % ASSOC_HASHSIZE;
  126.     return (hash1);
  127. }
  128.  
  129. /*
  130.  * locate symbol[subs], given hash of subs and type 
  131.  */
  132. static NODE *                /* NULL if not found */
  133. assoc_find(symbol, subs, hash1)
  134. NODE *symbol, *subs;
  135. int hash1;
  136. {
  137.     register NODE *bucket;
  138.  
  139.     for (bucket = symbol->var_array[hash1]; bucket; bucket = bucket->ahnext) {
  140.         if (cmp_nodes(bucket->ahname, subs))
  141.             continue;
  142.         return bucket;
  143.     }
  144.     return NULL;
  145. }
  146.  
  147. /*
  148.  * test whether the array element symbol[subs] exists or not 
  149.  */
  150. int
  151. in_array(symbol, subs)
  152. NODE *symbol, *subs;
  153. {
  154.     register int hash1;
  155.  
  156.     if (symbol->type == Node_param_list)
  157.         symbol = stack_ptr[symbol->param_cnt];
  158.     if (symbol->var_array == 0)
  159.         return 0;
  160.     subs = concat_exp(subs);
  161.     hash1 = hash_calc(subs);
  162.     if (assoc_find(symbol, subs, hash1) == NULL) {
  163.         free_temp(subs);
  164.         return 0;
  165.     } else {
  166.         free_temp(subs);
  167.         return 1;
  168.     }
  169. }
  170.  
  171. /*
  172.  * SYMBOL is the address of the node (or other pointer) being dereferenced.
  173.  * SUBS is a number or string used as the subscript. 
  174.  *
  175.  * Find SYMBOL[SUBS] in the assoc array.  Install it with value "" if it
  176.  * isn't there. Returns a pointer ala get_lhs to where its value is stored 
  177.  */
  178. NODE **
  179. assoc_lookup(symbol, subs)
  180. NODE *symbol, *subs;
  181. {
  182.     register int hash1, i;
  183.     register NODE *bucket;
  184.  
  185.     hash1 = hash_calc(subs);
  186.  
  187.     if (symbol->var_array == 0) {    /* this table really should grow
  188.                      * dynamically */
  189.         emalloc(symbol->var_array, NODE **, (sizeof(NODE *) *
  190.             ASSOC_HASHSIZE), "assoc_lookup");
  191.         for (i = 0; i < ASSOC_HASHSIZE; i++)
  192.             symbol->var_array[i] = 0;
  193.         symbol->type = Node_var_array;
  194.     } else {
  195.         bucket = assoc_find(symbol, subs, hash1);
  196.         if (bucket != NULL) {
  197.             free_temp(subs);
  198.             return &(bucket->ahvalue);
  199.         }
  200.     }
  201.     bucket = newnode(Node_ahash);
  202.     bucket->ahname = dupnode(subs);
  203.     bucket->ahvalue = Nnull_string;
  204.     bucket->ahnext = symbol->var_array[hash1];
  205.     symbol->var_array[hash1] = bucket;
  206.     return &(bucket->ahvalue);
  207. }
  208.  
  209. void
  210. do_delete(symbol, tree)
  211. NODE *symbol, *tree;
  212. {
  213.     register int hash1;
  214.     register NODE *bucket, *last;
  215.     NODE *subs;
  216.  
  217.     if (symbol->var_array == 0)
  218.         return;
  219.     subs = concat_exp(tree);
  220.     hash1 = hash_calc(subs);
  221.  
  222.     last = NULL;
  223.     for (bucket = symbol->var_array[hash1]; bucket; last = bucket, bucket = bucket->ahnext)
  224.         if (cmp_nodes(bucket->ahname, subs) == 0)
  225.             break;
  226.     free_temp(subs);
  227.     if (bucket == NULL)
  228.         return;
  229.     if (last)
  230.         last->ahnext = bucket->ahnext;
  231.     else
  232.         symbol->var_array[hash1] = bucket->ahnext;
  233.     deref = bucket->ahname;
  234.     do_deref();
  235.     deref = bucket->ahvalue;
  236.     do_deref();
  237.     freenode(bucket);
  238. }
  239.  
  240. struct search *
  241. assoc_scan(symbol)
  242. NODE *symbol;
  243. {
  244.     struct search *lookat;
  245.  
  246.     if (!symbol->var_array)
  247.         return 0;
  248.     emalloc(lookat, struct search *, sizeof(struct search), "assoc_scan");
  249.     lookat->numleft = ASSOC_HASHSIZE;
  250.     lookat->arr_ptr = symbol->var_array;
  251.     lookat->bucket = symbol->var_array[0];
  252.     return assoc_next(lookat);
  253. }
  254.  
  255. struct search *
  256. assoc_next(lookat)
  257. struct search *lookat;
  258. {
  259.     for (; lookat->numleft; lookat->numleft--) {
  260.         while (lookat->bucket != 0) {
  261.             lookat->retval = lookat->bucket->ahname;
  262.             lookat->bucket = lookat->bucket->ahnext;
  263.             return lookat;
  264.         }
  265.         lookat->bucket = *++(lookat->arr_ptr);
  266.     }
  267.     free((char *) lookat);
  268.     return 0;
  269. }
  270.